package KEY;

import org.junit.jupiter.api.Test;

/**
 * @Author: Siantar
 * @Date: 2023-11-13-13:24
 * @Description: 1.0
 */
public class segmentTree {
    class Node {
        Node left,right;
        int value,change;
    }

    public Node root=new Node();
    public int N = (int) 1e9;

    public void update(Node node, int start, int end, int left, int right, int change) {
        if (left <= start && end <= right) {
            node.value += (end - start + 1) * change;
            node.change = change;
            return;
        }
        int mid = start + ((end - start) >> 1);
        pushDown(node, mid - start + 1, end - mid);
        if (left <= mid) update(node.left, start, mid, left, right, change);
        if (mid < right) update(node.right, mid + 1, end, left, right, change);
        pushUp(node);
    }

    public int query(Node node, int start, int end, int left, int right) {
        if (left <= start && end <= right) {
            return node.value;
        }
        int mid = start + ((end - start) >> 1), ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (left <= mid) ans += query(node.left, start, mid, left, right);
        if (mid < right) ans += query(node.right, mid + 1, end, left, right);
        return ans;
    }


    public void pushUp(Node node) {
        node.value = node.left.value + node.right.value;
    }

    public void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.change == 0) return;
        node.left.value += node.change * leftNum;
        node.right.value += node.change * rightNum;
        node.left.change += node.change;
        node.right.change += node.change;
        node.change=0;
    }

    @Test
    public void test() {
        update(root,1,N,1,5,1);
        update(root,1,N,2,3,1);
        update(root,1,N,2,2,1);
        int a=query(root,1,N,2,3);
        System.out.println(a);
    }

}
